#include"Heap.h"

//堆的初始化
void HeapInit(HP* php)
{
	php->_a = NULL;
	php->_capacity = 0;
    php->_size = 0;
}

// 堆的销毁
void HeapDestory(HP* php)
{
	assert(php);
	assert(php->_size > 0);

	free(php->_a);
	php->_capacity = 0;
	php->_size = 0;
}

//向上调整
void AdjustUp(HPDataType* a, int child)
{

	int parent = (child - 1) / 2;

	while (parent > 0 && a[child] < a[parent])
	{
		Swap(&a[child], &a[parent]);
		child = parent;
		parent = (child - 1) / 2;
	}

}

//向下调整
void AdjustDown(HPDataType* a, int n,int parent)
{
	int child = parent * 2 + 1;
	
	if (a[child+1] < a[child])
	{
		child++;
	}

	while (child < n && a[parent] > a[child])
	{
		Swap(&a[parent], &a[child]);
		parent = child;
		child = parent * 2 + 1;
		if (child+1<n&&a[child + 1] < a[child])
		{
			child++;
		}
	}
}

// 堆的插入
void HeapPush(HP* php, HPDataType x)
{
	assert(php);


	//扩容
	if (php->_size == php->_capacity)
	{
		int newcapacity = php->_capacity == 0 ? 4 : php->_capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc
		(php->_a, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		php->_a = tmp;
		php->_capacity = newcapacity;
	}

	php->_a[php->_size++] = x;
	AdjustUp(php->_a, php->_size - 1);

}

// 堆的删除
void HeapPop(HP* php)
{
	assert(php);
	assert(php->_size > 0);

	Swap(&php->_a[0], &php->_a[php->_size--]);
	
	AdjustDown(php->_a, php->_size, 0);

}

// 取堆顶的数据
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->_size > 0);

	return php->_a[0];
}

// 堆的数据个数
int HeapSize(HP* php)
{
	assert(php);
	assert(php->_size > 0);

	return php->_size - 1;
}

// 堆的判空                    不空返回1
int HeapEmpty(HP* php)
{
	assert(php);
	if (php->_size > 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}

}

// 对堆数组进行堆排序  //降序
void HeapSort(HPDataType* a, int n)
{
	//降序, 建小堆
	for (int i = 0; i < n; i++)
	{
		AdjustUp(a, i);
	}

	int i = 0;
	int size = n;

	for (size = n; size > 0; size--)
	{
		Swap(&a[size-1], &a[0]);
		AdjustDown(a, size-1,0);
	}
	
}

//TopK问题
void CreateNDate()
{
	// 造数据
	int n = 10000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (size_t i = 0; i < n; ++i)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

void PrintTopK(int k)
{
	FILE* pf = fopen("data.txt", "r");
	
	int a[k];
	
	int i = 0;
	while (i<k)
	{
		fscanf(pf, "%d", a[i++]);
		
	}
	//建小堆
	for ( i = 0; i < k; i++)
	{
		AdjustUp(a, i);
	}
	int x;
	while (1)
	{
		if (feof(pf))
		{
			break;
		}
		fscanf(pf, "%d", &x);
		
		if (x > a[0])
		{
			a[0] = x;
			AdjustDown(a, k, 0);
		}
		
	}
}

